package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.ListNode;
import kyssion.leetcode.util.ShowUtil;

public class code148_排序链表 {
    public static void main(String[] args) {
        ListNode listNode = ListNode.createListNode(new int[]{
                1, 3, 2, 2, 3, 4, 5, 2, 1
        });

        listNode = new code148_排序链表().sortList(listNode);
        ShowUtil.showNode(listNode);
    }

    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode item = head;
        ListNode head1 = head;
        while (head1 != null && head1.next != null) {
            item = item.next;
            head1 = head1.next.next;
        }

        if (item.next == null) {
            if (head.val > head.next.val) {
                ListNode i = head.next;
                head.next.next = head;
                head.next = null;
                return i;
            }
            return head;
        }
        head1 = item.next;
        item.next = null;
        head = sortList(head);
        head1 = sortList(head1);
        item = new ListNode(-1);
        ListNode p = item;
        while (true) {
            if (head == null) {
                item.next = head1;
                break;
            }
            if (head1 == null) {
                item.next = head;
                break;
            }

            if (head.val < head1.val) {
                item.next = head;
                item = item.next;
                head = head.next;
            } else {
                item.next = head1;
                item = item.next;
                head1 = head1.next;
            }
        }
        return p.next;
    }
}
